import { Compare, defaultCompare, ICompareFunction } from "./util";
import Node from './node';

export default class BinarySearchTree<T> {
    // 1. 构造函数初始化 有初始值
    // 2. compareFn 是可以被继承的属性
    protected root: Node<T> | undefined ;
    constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
        this.root = undefined
    }
    insert(key: T):void {
        if (this.root == undefined) {
            this.root = new Node(key)
        } else {
            this.insertNode(this.root, key)
        }
    }
    insertNode(node: Node<T>, key: T): void {
        if (this.compareFn(key, node.key) === Compare.LESS_THEN) {
            if (node.left == undefined) {
                node.left = new Node(key, node)
            } else {
                this.insertNode(node.left, key)
            }
        } else {
            if (node.right == undefined) {
                node.right = new Node(key, node)
            } else {
                this.insertNode(node.right, key)
            }
        }
    }
    max(): Node<T>{
        return this.maxNode(<Node<T>>this.root)
    }
    private maxNode(node: Node<T>) {
        let current = node 
        while(current != undefined && current.right != undefined) {
            current = current.right
        }
        return current
    }
    min(): Node<T> {
        return this.minNode(<Node<T>>this.root)
    }
    private minNode(node: Node<T>): Node<T> {
        let current = node;
        while(current != undefined && current.left != undefined) {
            current = current.left
        }
        return current
    }
}